// Created by WXX on 2021/9/8 9:22
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * 执行用时：164 ms, 在所有 C++ 提交中击败了87.92%的用户
 * 内存消耗：80.1 MB, 在所有 C++ 提交中击败了36.91%的用户
 */
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
        vector<pair<int, int>> q;
        int n = profits.size();
        for (int i = 0; i < n; i++) q.push_back({capital[i], profits[i]});
        sort(q.begin(), q.end());

        priority_queue<int> heap;
        int i = 0;  // 记录可选的资本
        while (k--) {
            while (i < n && q[i].first <= w) heap.push(q[i].second), i++;
            if (heap.empty()) break;
            auto t = heap.top();
            w += t;
            heap.pop();
        }
        return w;
    }
};

int main() {

    vector<int> profits = {1, 2, 3};
    vector<int> capital = {0, 1, 1};
    cout << Solution().findMaximizedCapital(2, 0, profits, capital) << endl;

    return 0;
}
